#define _CRT_SECURE_NO_WARNINGS 1

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

struct Node
{
	int val;
	struct Node* next;
	struct Node* random;
};

struct Node* creat(int x)
{
	struct Node* newnode = (struct Node*)malloc(sizeof(struct Node));
	if (newnode == NULL)
	{
		perror("malloc");
		exit(-1);
	}
	newnode->val = x;
	newnode->next = NULL;
	newnode->random = NULL;
	return newnode;
}

struct Node* copyRandomList(struct Node* head) {
    assert(head);
    struct Node* cur = head;
    while (cur)
    {
        struct Node* newnode = (struct Node*)malloc(sizeof(struct Node));
        if (newnode == NULL)
        {
            perror("malloc");
            exit(-1);
        }
        struct Node* next = cur->next;
        newnode->next = next;
        newnode->val = cur->val;
        cur->next = newnode;
        cur = next;
    }
    cur = head;
    while (cur)
    {
        if (cur->random == NULL)
            cur->next->random = NULL;
        else
            cur->next->random = cur->random->next;
        cur = cur->next->next;
    }
    cur = head;
    struct Node* ret = cur->next;
    while (cur)
    {
        struct Node* Next = cur->next;
        cur->next = cur->next->next;
        if (cur->next == NULL)
            Next->next = NULL;
        else
            Next->next = cur->next->next;
        cur = cur->next;
    }
    return ret;
}

void test()
{
	struct Node* head1 = creat(1);
	struct Node* head2 = creat(2);
	struct Node* head3 = creat(3);
	struct Node* head4 = creat(4);
	head1->next = head2;
	head2->next = head3;
	head3->next = head4;
	head1->random = head3;
	head2->random = NULL;
	head3->random = head2;
	head4->random = head1;
    struct Node* copy = copyRandomList(head1);
}

int main()
{
	test();
	return 0;
}